/* 
 * File:   dmm.cpp
 * Author: Chen Liu     Student Number:3996591
 * 
 * Created on August 27, 2012, 2:27 PM
 */
#include <iostream>
#include <cstdlib>
#include "dmm.h"

using namespace std;

DMM::DMM(WORD *memory, int words, Policy type)
{
    policy=type;
    startAddr=memory;
    capacity=words;
    bytesAlloc=0;
    blockAlloc=0;
    CmpsCounter=0;

    WORD *pMem=memory;
    *pMem=FREE;
    *(pMem+1)=words-4;
    pMem+=words-2;
    *pMem=FREE;
    *(pMem+1)=words-4;
    MemSeg freeSeg;
    freeSeg.address=memory;
    freeSeg.words=words-4;
    freeSegList.push_back(freeSeg);
    current = freeSegList.begin();
}

char* DMM::New(int size)
{
    if(freeSegList.empty()) //out of memory
    {
        return NULL;
    }
    
    if(size%4!=0)
    {
        cout<<"The memory should fit the 4 byte word boundary."<<endl;;
        return NULL;
    }
    int words=size/4;
    char* pRetVal;
    
    
    if(policy==eFirstFit)
    {
        list<MemSeg>::iterator it=freeSegList.begin(); 
        
        while(Compare(it->words,words,CmpsCounter)<0)
            ++it;
        if(it==freeSegList.end())
        {
            return NULL;
        }
        pRetVal=(char*)(it->address+2);
        if(it->words-words>=6)  // split the large free segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            *(pAddr+1)=words;
            pAddr+=words+2;
            *pAddr=USED;
            *(pAddr+1)=words;
            // count byte and block allocate
            bytesAlloc+=words*4;
            blockAlloc++;

            // new free segment
            pAddr+=2;
            *pAddr=FREE;
            *(pAddr+1)=it->words-words-4;
            *(it->address+it->words+3)=it->words-words-4;

            // edit the list
            it->address=pAddr;
            it->words=it->words-words-4;
            
        }
        else        // allocate the whole segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            pAddr+=it->words+2;
            *pAddr=USED;
            // count byte and block allocate
            bytesAlloc+=it->words*4;
            blockAlloc++;

            // remove from list
            freeSegList.erase(it);
            
        }
    }
    
    
    else if(policy==eNextFit){
        
        list<MemSeg>::iterator it = current;
        
        while(Compare(it->words,words,CmpsCounter)<0)
            ++it;
       
        if(it==freeSegList.end())//search from the begin 
        {
            
                it=freeSegList.begin();
                while(Compare(it->words,words,CmpsCounter)<0)
                    ++it;
             
                if(it==freeSegList.end()){
                    return NULL;
                }           
        }

        
        pRetVal=(char*)(it->address+2);
        if(it->words-words>=6)  // split the large free segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            *(pAddr+1)=words;
            pAddr+=words+2;
            *pAddr=USED;
            *(pAddr+1)=words;
            
            // count byte and block allocate
            bytesAlloc+=words*4;
            blockAlloc++;
            
            // new free segment
            pAddr+=2;
            *pAddr=FREE;
            *(pAddr+1)=it->words-words-4;
            *(it->address+it->words+3)=it->words-words-4;
            
            // edit the list
            it->address=pAddr;
            it->words=it->words-words-4;
        }
        else        // allocate the whole segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            pAddr+=it->words+2;
            *pAddr=USED;
            
            // count byte and block allocate
            bytesAlloc+=it->words*4;
            blockAlloc++;
            
            // remove from list
            it = freeSegList.erase(it); //remember to check the iterator is valid
        }
        current = it; //record the current iterator
    }
    
    
    else if(policy==eBestFit)
    {
        list<MemSeg>::iterator it=freeSegList.begin(); 
        while(Compare(it->words,words,CmpsCounter)<0)
            ++it;
        if(it==freeSegList.end())
        {
            return NULL;
        }
        pRetVal=(char*)(it->address+2);
        if(it->words-words>=6)  // split the large free segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            *(pAddr+1)=words;
            pAddr+=words+2;
            *pAddr=USED;
            *(pAddr+1)=words;
            
            // count byte and block allocate
            bytesAlloc+=words*4;
            blockAlloc++;

            // new free segment
            pAddr+=2;
            *pAddr=FREE;
            *(pAddr+1)=it->words-words-4;
            *(it->address+it->words+3)=it->words-words-4;
            MemSeg newFreeSeg;
            newFreeSeg.address=pAddr;
            newFreeSeg.words=it->words-words-4;

            // remove origin segment from list
            freeSegList.erase(it);
            // find the position and insert the new free segment
            it=freeSegList.begin();
            while(it!=freeSegList.end() && Compare(it->words,newFreeSeg.words,CmpsCounter)<0)
                ++it;
            freeSegList.insert(it, newFreeSeg);
            
        }
        else        // allocate the whole segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            pAddr+=it->words+2;
            *pAddr=USED;
            // count byte and block allocate
            bytesAlloc+=it->words*4;
            blockAlloc++;

            // remove from list
            freeSegList.erase(it);           
        }
    }
    
    
    else if(policy==eWorstFit)
    {
        list<MemSeg>::iterator it=freeSegList.begin(); 
        while(Compare(it->words,words,CmpsCounter)<0)
            ++it;
        pRetVal=(char*)(it->address+2);
        if(it==freeSegList.end())
        {
            return NULL;
        }
        if(it->words-words>=6)  // split the large free segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            *(pAddr+1)=words;
            pAddr+=words+2;
            *pAddr=USED;
            *(pAddr+1)=words;
            
            // count byte and block allocate
            bytesAlloc+=words*4;
            blockAlloc++;

            // new free segment
            pAddr+=2;
            *pAddr=FREE;
            *(pAddr+1)=it->words-words-4;
            *(it->address+it->words+3)=it->words-words-4;
            MemSeg newFreeSeg;
            newFreeSeg.address=pAddr;
            newFreeSeg.words=it->words-words-4;

            // remove origin segment from list
            freeSegList.erase(it);
            // find the position and insert the new free segment
            it=freeSegList.begin();
            while(it!=freeSegList.end() && Compare(it->words,newFreeSeg.words,CmpsCounter)>0)
                ++it;
            freeSegList.insert(it, newFreeSeg);
            
        }
        else        // allocate the whole segment
        {
            WORD *pAddr=it->address;
            *pAddr=USED;
            pAddr+=it->words+2;
            *pAddr=USED;
            
            // count byte and block allocate
            bytesAlloc+=it->words*4;
            blockAlloc++;

            // remove from list
            freeSegList.erase(it);
        }
    }

    return pRetVal;
}

void DMM::Delete(char *address)
{
    int lsign=0,rsign=0;
    if(address==NULL)
        return;

    WORD* pAddr=((WORD*)address)-2;     
    WORD words=*(pAddr+1);

    if(*pAddr!=USED || *(pAddr+words+2)!=USED || *(pAddr+words+3)!=words)
    {
        cerr<<"You're trying to free a invalid memory block.\n";
        exit(-1);
    }
    
    // count byte and block allocate
    bytesAlloc-=words*4;

    WORD freeSegWords=words;
    WORD *pHead=pAddr, *pTail=pAddr+words+2;
    MemSeg memSeg;
    list<MemSeg>::iterator it=freeSegList.begin();

    if(pAddr-2>startAddr && *(pAddr-2)==FREE)    // merge the left free segment
    {
        pHead=pAddr-4-*(pAddr-1);
        freeSegWords+=*(pHead+1)+4;


        // remove the small free segment
        it=freeSegList.begin();
        while(pHead!=it->address){
            ++it;
        }
        
        if(it==current){//check the delete operation will effect the iterator
            lsign=1;
        }
        it = freeSegList.erase(it);
        if(lsign==1){//renew the iterator: current
            current = it;
        }
    }

    if(pAddr+words+8<startAddr+capacity && *(pAddr+words+4)==FREE)  // merge the right free segment
    {
        pTail=pAddr+words+6+*(pAddr+words+5);
        freeSegWords+=*(pTail+1)+4;

        // remove the small free segment
        it=freeSegList.begin();
        while(pAddr+words+4!=it->address)
            ++it;
        
        if(current == it){
            rsign=1;
        }
        it = freeSegList.erase(it);
        if(rsign==1){//renew the iterator: current
            current = it;
        }
    }
    *pHead=FREE;
    *(pHead+1)=freeSegWords;
    *pTail=FREE;
    *(pTail+1)=freeSegWords;
    // add the merged free segment to list
    memSeg.address=pHead;
    memSeg.words=*(pHead+1);
    it=freeSegList.begin();
    if(policy==eFirstFit)
    {
        while(it!=freeSegList.end() && it->address<memSeg.address)
            ++it;
        freeSegList.insert(it, memSeg);
    }
    if(policy==eNextFit)
    {
        while(it!=freeSegList.end() && it->address<memSeg.address)
            ++it;
        freeSegList.insert(it, memSeg);
    }
    else if(policy==eBestFit)
    {
        while(it!=freeSegList.end() && (it->words < memSeg.words))
            ++it;
        freeSegList.insert(it, memSeg);
    }
    else if(policy==eWorstFit)
    {
        while(it!=freeSegList.end() && (it->words < memSeg.words))
            ++it;
        freeSegList.insert(it, memSeg);
    }
}

void DMM::GetStats(int &bAlloc, int &blAlloc, int &Cmps)
{
    bAlloc=bytesAlloc;    
    blAlloc=blockAlloc;
    Cmps=CmpsCounter;
}

int DMM::Compare(WORD word1, WORD word2, int &counter)
{
    ++counter;
    return word1-word2;
}

